class Solution {
    ArrayList<String> result = new ArrayList<>();
    
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);  // bbaad  aabbd
        dfs(chars, new StringBuilder());
        return result.toArray(new String[0]);
    }
    public void dfs(char[] chars, StringBuilder stringBuilder) {
        if (chars.length == stringBuilder.length()) {
            result.add(stringBuilder.toString());
        } else {
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                if (c == '/') continue; //判断该索引的值是否被用过   / 代表被用过
                if (i > 0 && chars[i] == chars[i - 1] && chars[i - 1] != '/') continue; //剪枝
                stringBuilder.append(c);
                chars[i] = '/'; // 标记成已经用过
                dfs(chars, stringBuilder);
                // 回溯 需要擦除之前的痕迹
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                chars[i] = c;
            }
        }
    }
}